1922C - Closest Cities - CodeForces Solution

//baadshah
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double
#define pb push_back
#define mp make_pair
#define INF LLONG_MAX

// Custom Macros
#define fr(i, a, b) for (int i = (a); i < (b); ++i)
#define rfr(i, a, b) for (int i = (a); i >= (b); --i)
#define dbg(x) cout << #x << " = " << x << endl;

const ll MOD = 1e9 + 7;
// Custom Functions
void solve() {
    int n;
    cin>>n;
    vector<int>v(n);
    for (int i =0;i<n;i++){
        cin>>v[i];
    }
    int q;
    cin>>q;
            vector<int>x;
        vector<int>y;
        ll ans =1;
        x.push_back(1);
        for (int i =1;i<n-1;i++){

            int diff1 = v[i]-v[i-1];
            int diff2 = v[i+1]-v[i];

            if (diff2<diff1){
                ans+=1;


            }
            else {
                ans +=diff2;
            }

            x.push_back(ans);



        }

        ans =1;
        y.push_back(1);

        for (int i =n-2;i>=1;i--){

            int diff1 = v[i]-v[i-1];
            int diff2 = v[i+1]-v[i];

            if (diff1<diff2){
                ans+=1;
                


            }
            else {
                ans +=diff1;
            }

            y.push_back(ans);



        }


    while(q--){

        int a,b;
        cin>>a>>b;


        int val =0;


        if (a<b){
            int i = a-1;
            int diff = b-a-1;

            int ind = i+diff;

            val = x[ind];
            if (i>0)val = val-x[i-1];

        }
        else {
            int i = n-a;


            int diff = a-b-1;
            int ind = i+diff;
            // dbg(i);
            // dbg(diff);
            // dbg(ind);

            val = y[ind];
            if (i>0)val =val-y[i-1];

        }

        cout<<val<<endl;



    }

    // Your code here
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}